package demo.lintcode.dp;

public class P125 {

    public static void main(String[] args) {
        P125 p125 = new P125();
        p125.backPackII(100, new int[]{77,22,29,50,99}, new int[]{92,22,87,46,90});
    }

    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        int dp[][] = new int[A.length][m + 1];

        for (int i = 0; i < A.length; i++) {
            dp[i][0] = 0;
        }

        for (int j = 1; j <= m; j++) {
            dp[0][j] = j >= A[0] ? V[0] : -1;
        }

        int max = 0;
        for (int i = 1; i < A.length; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = -1;

                if (m >= A[i]) {
                    //第i个元素不算，就是 dp[i - 1][j]
                    dp[i][j] = dp[i - 1][j];
                    //第i个元素算 j - A[i] >= 0
                    if (j - A[i] >= 0 && dp[i - 1][j - A[i]] != -1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i]] + V[i]);
                    }
                }
                max=Math.max(dp[i][j],max);
            }
        }

        return max;
    }
}
